/**
* @description: 周赛309 t2
* @author hewei
* @date 2022/9/4 10:35
* @version 1.0
*/

public class NumberOfWays {

    public int numberOfWays(int startPos, int endPos, int k) {
        int mod = (int) (1e9 + 7);
        long[][] dp = new long[k + 1][2 * k + 1];
        dp[0][k] = 1L;
        for (int i = 1; i < k + 1; i++) {
            for (int j = startPos - i; j < startPos + i + 1; j++) {
                dp[i][j - startPos + k] = ((j - startPos + k - 1 < 0 ? 0 : dp[i - 1][j - startPos + k - 1]) + (j - startPos + k + 1 >= 2 * k + 1 ? 0 : dp[i - 1][j - startPos + k + 1])) % mod;
            }
        }
        if (endPos - startPos + k >= 2 * k + 1) return 0;
        return (int) (dp[k][endPos - startPos + k] % mod);
    }
}
